package leetcode.code0629;

import leetcode.helper.HelpDebug;

public class Solution extends Solution629 {

	public static int mod = (int) 1e9 + 7;

	@Override
	public int kInversePairs(int n, int k) {
		int[][] dp = new int[n + 1][k + 1];
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			dp[i][0] = 1;
			for (int j = 1; j <= k; j++) {
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
				if (i <= j) {
					dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + mod) % mod;
				}
			}
		}
		HelpDebug.print(dp);
		return dp[n][k];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		int r = so.kInversePairs(3, 2);
		System.out.println(r);
	}

}
